from typing import List


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        first = [matrix[x][0] for x in range(0, len(matrix))]
        line = self.binary_search_le(first, target)
        print(line)
        idx = self.binary_search_eq(matrix[line], target)
        return idx > -1

    def binary_search_le(self, nums: List[int], target: int):
        left = -1
        right = len(nums)
        while left + 1 < right:
            mid = (left + right) // 2
            if nums[mid] <= target:
                left = mid
            else:
                right = mid
        return left

    def binary_search_eq(self, nums: List[int], target: int):
        left = -1
        right = len(nums)
        while left + 1 < right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid
            else:
                left = mid
        return -right - 1
